The present invention relates to the management of storage media and, more particularly, to a driver that makes efficient use of a storage medium, such as a flash memory device, accesses of which are relatively slow and must be checked for successful completion.
Flash memory devices are compact, non-volatile data storage devices that are commonly used as substitutes for block memory devices such as hard disks. There are two main types of flash memory devices: NOR flash devices and NAND flash devices.
In a NOR flash device, reading is random access and fast (tens of nanoseconds), similar to RAM. Writing also is random access as in RAM, but is somewhat slow (a few microseconds). Erasing must be done in relatively large units called “blocks”, and is very slow (a few hundred milliseconds).
In a NAND flash device, reading is serial rather than random access, and is somewhat slow (typically 10 to 15 microseconds). Writing must be done in medium-size units called “pages” and is slow (a few hundred microseconds). Erasing must be done in blocks, and is slow (a few milliseconds).
Note that the use of the word “block” to refer to the erasable units of a flash memory device should not be confused with the use of the word “block” in the term “block memory device”. The “block” nature of a block memory device refers to the fact that the device driver exports an interface that exchanges data only in units that are integral multiples of a fixed-size, smaller unit that typically is called a “sector”.
In order for a flash memory device to emulate a block memory device, a software flash device driver, also called a flash management system, must be provided. The flash device driver exports the Application Programming Interface (API) of a block device driver and handles all the flash management details internally. Such a flash device driver allows application software that stores data on hard disks, for example by using a file system such as Microsoft FAT or NTFS, to access a flash memory device as though it were a hard disk, with no changes to the software applications. Exemplary flash device drivers are described by Ban in U.S. Pat. Nos. 5,404,485 and 5,937,425, both of which are incorporated by reference for all purposes as if fully set forth herein. Typically, such flash device drivers use some form of address mapping to translate the logical or virtual addresses used by the higher level software to the physical addresses of the flash memory device hardware. A flash device driver may include its own file system, may operate under the native file system of the host operating system, or may interact directly with applications and so bypass the use of a file system.
A flash device driver receives calls from application software that requests the reading and writing of data in units of sectors. Typically, a sector is 512 bytes long. A request may be for a single sector or for multiple sectors per call. Each sector corresponds, in size, to a physical portion of the flash memory device that is referred to herein as a “page”. In the case of a NAND flash device, the pages are discrete physical units of the device. In the case of a NOR flash device, in which both reading and writing is random access, a “page” is just a physical portion of the device that is capable of storing a sector's worth of data, and the various “pages” are not necessarily separate and discrete.
A typical format for a command that reads a single sector is:
Status=ReadSector(bDriveID,wSectorNumber,pDataBuffer) and a typical format for a command that writes a single sector is:
Status=WriteSector(bDriveID,wSectorNumber,pDataBuffer) where Status is set to a success/failure code on return from the call; bDriveID identifies the data storage device (to allow more than one data storage device to be used); wSectorNumber identifies the logical sector number to be read from or to be written to; and pDataBuffer is a pointer that points to a buffer that receives that data read from the data storage device or that contains the data to be written to the data storage device.
All prior art flash device drivers process such requests by accessing a flash memory device according to the specifics of that device, and then waiting for the completion of the relatively slow flash device operation. The following pseudocode illustrates what a prior art flash device driver must do in a WriteSector command:    Start WriteSector:            Translate wSectorNumber to the physical address currently allocated for that logical address.        Send one command byte to the flash memory device, indicating the start of data input.        Send four bytes of physical address to the flash memory device.        Send the data bytes (typically including both the application software data bytes from pDataBuffer and some control bytes attached to the data by the flash device driver) that are to be written to the flash memory device.        Send one command byte to the flash memory device to initiate auto-programming by the flash memory device. While the flash memory device is busy programming the data bytes into the flash cells, the flash memory device displays a “busy” status.        Wait until the “busy” status of the flash memory device terminates. Typically, this is done by looping over a command that reads the flash memory device status and exits the loop if the status is not “busy”.        Query the flash memory device for operation success.        If success:                    Then return from the call while setting Status to the success code                        Else:                    Mark the failed physical page as bad to avoid reusing that page.            Re-define the address mapping so that wSectorNumber is mapped to a different physical address.            Go to Start WriteSector.                        
The problem with this method of writing to a flash memory device is that while the flash memory device is busy programming the data bytes into the flash cells, the calling software application is stalled. Consider, for example, an application that uses a NAND flash device for storing data, via the following C-like pseudocode:
For ( I=0; I<1000; I++){generate 512 bytes of new data;write new data to flash;}Assuming a one millisecond page writing time, assuming that it takes the processor one millisecond to generate 512 bytes of new data, and ignoring both the time that the processor uses to run the looping code and the flash driver code and the time that it takes to pass the data from the processor to the flash memory device via the system bus, it follows that each iteration of this loop takes two milliseconds, not the one millisecond that the processor needs to generate the new data. This is because the processor is stalled while the flash memory device is busy programming the new data bytes into flash cells.
The reason that prior art flash device drivers insist on waiting until a flash operation completes before freeing the calling software to continue its own processing is that the operation may fail. For example, if a write operation fails, the flash device driver must retry the operation in a way that eventually allows the operation to succeed. Exactly how this is done varies from flash device driver to flash device driver, but it must be done. If a flash device driver does not verify the success of an operation before returning control to the calling application, then a flash failure might go undetected. Even if the flash failure would be detected later, there would be no way to correct it because by the time the failure is detected the application software is dealing with different data.
An alternative in a multi-tasking system is to have the flash memory device generate an interrupt upon completing its operation, to have the flash device driver yield control of the processor immediately following the beginning of the flash operation, and, when the flash device driver regains control following detection of the interrupt, to have the flash device driver check for failure and complete its part of the operation as above (including recovering from failure if necessary). This improves the efficiency of the system as a whole, because the processor is free to deal with tasks other than the application that called the flash device driver while the flash memory device is busy; but the calling application itself still is stalled while the flash memory device is busy.
There is thus a widely recognized need for, and it would be highly advantageous to have, a driver, of a flash memory device, that frees a calling application to continue its own processing while the flash memory device performs the called operation.